【题解】 [HNOI2019]多边形 组合数学 luoguP5288 | Qiuly's blog!

【题解】 [HNOI2019]多边形 组合数学 luoguP5288

Posted on | In | Comments:

$\texttt{HNOI2019}$ 终于改出来一道题目了……感谢 $JerryC$ 跟我一起讨论，不然我也看不懂题解。这题真的是 $\texttt{HNOI2019}$ 最可做的题啊，可想而知 $\texttt{HNOI2019}$ 有多么毒瘤了。

$orz yyb$ ，感谢 $yyb$ 大佬的题解。

这一题一共有两问，并且部分分也比较多，接下来我们一起来逐一攻破这些特殊条件。

1.只有第一问且 $m=0$ 的情况

其实这个时候我们可以发现，最终的答案是要满足所有的点都连向 $n$ 。

对于每一次旋转操作，可以让 一个没有连向 $n$ 的点连向 $n$ ，并且一次旋转操作也最多可以使得一个没有连向 $n$ 的点连向 $n$ 。既然要求最少步数，我们考虑最优情况：每一次旋转都有一个新的点连向 $n$ 。这个时候最终需要的最少步数显然就是 $n-1-$已经与 $n$ 连接了的点数，为什么 $-1$ ？因为最终需要连向 $n$ 的点不包括 $n$ 。(ps：这里指的已经与 $n$ 连接了的点数其实包括 $1$ 与 $n-1$) 。

至于代码实现的话，我们用个 $vector$ 来存连接的点，最后统计一下 $size$ 即可。

2.有两问且 $m=0$ 的情况

初始局面的第一问我们已经解决了，现在我们来看看怎么解决初始局面的第二问。

假设当前与 $n$ 连接了的点的集合为 $S=\{a_1,a_2,\cdots ,a_s\}$ ，这个时候我们将 $1$ 到 $n$ 分成若干个区间：$[1,a_1],[a_1,a_2],\cdots,[a_{s-1},a_s],[a_s,n-1]$ ，我们会发现，每一次旋转操作的四个点一定属于同一个区间 。在最终状态，每一个区间中的所有的点都是连向 $n$ 的。

那么我们考虑计算每一个区间的操作序列，我们设 $[a_i,a_{i+1}]$ 区间的操作序列长度为 $sz(a_i)$ 。注意这个操作序列指的就是一个区间从初始状态到最终状态的所有旋转操作组成的序列。

我们现在考虑方案数，假设我们知道了 $sz(a_i),sz(a_{i+1})$ ，也就是区间 $[a_i,a_{i+1}]$ 和区间 $[a_{i+1},a_{i+2}]$ 的操作序列的长度。那么使得这两个区间都到达最终状态的方案数显然为 $C_{sz(a_i)+sz(a_{i+1})}^{sz(a_i)}$，当然也是 $C_{sz(a_i)+sz(a_{i+1})}^{sz(a_{i+1})}$ 。

这下子计算就变得简单多了，但是我们怎么求出使得单个区间变为最终状态的方案数以及当个区间的操作序列长度呢？这个时候我们可以将每一个区间 $[a_i,a_{i+1}]$ 建成一棵二叉树，每一次将 $[a_i,a_{i+1}]$ 拆成 $[a_i,p],[p,a_{i+1}]$ ，在树中这两个子区间就是 $[a_i,a_{i+1}]$ 的两个儿子。

这下子使得 $[a_i,a_{i+1}]$ 变为最终状态的方案数显然可以从其树中的两个儿子得出了，计算的方法和上面同理。

至于这个 $p$ ，假设当前区间为 $l,r$ ，我们可以选择 第一个比 $l+1$ 大且与 $r$ 连了边的点 ，那么这个时候可以理解为 拆掉 $p,r$ 这条边，然后连起来 $p,n$ 这条边 ，于是 $l,p$ 可以作为一个区间了，$p,r$ 也可以作为一个区间了。

为什么一定要选择第一个比 $l+1$ 大且与 $r$ 连了边的点呢？我们考虑两个点 $a$ 和 $b$ ，其中 $a$ 就是第一个比 $l+1$ 大且与 $r$ 连了边的点，$b$ 则是一个小于 $r$ 大于 $a$ 并且和 $r$ 连了边的点 。如果这个时候选择将 $b,r$ 断开连接 $b,n$ 的话，线段 $a,r$ 和线段 $b,n$ 显然会交叉 ，那么就不合法了。所以我们选择第一个比 $l+1$ 大且与 $r$ 连了边的点，这样至少是合法的。当然如果这个点大于 $r$ 了就没办法了。

代码的话一个 $dfs$ 可以搞定。

3.$m>0$ 且只有第一问的情况

首先我们会发现，第一问的答案其实就是我们的树的结点个数。

然后考虑这个旋转操作，现在有 $a<b<c<d​$ ，我们需要求出的就是 $(a,c)​$ 旋转对第一问带来的变化。

既然 $a,c$ 是连了边的，那么在树中也一定有一个节点代表 $[a,c]$ 区间，我们先在树中找到这个节点，然后再分两种情况来讨论。

一.该节点在树中有父节点

我们将图画出来：

（左边的是原来的，右边的是经过了 $(a,c)$ 旋转的）

可以发现，旋转之后我们损失了 $(a,c)$ 节点，但是多了个 $(b,d)$ 节点，我们的节点数实际上是没有变的。也就是说我们第一问的答案没有变。

二.该节点在树中没有父节点

这个时候 $a,c$ 肯定都是已经连向了 $n$ 的，不然不可能没有父节点。那么这个时候 $d$ 要不是 $n$ 要不是其他区间的点了。上文已经讲了，旋转操作只可能在一个区间内进行，也就是说 $d$ 只能等于 $n$ 。

那么 $d=n$ 的话树会怎么变换呢？很显然，$(a,c)$ 会消失，剩下的就是 $(a,b)$ 和 $(b,c)$ 。这个时候是少了一个点的，那么第一问的答案就要减一了。

如果从多边形的角度理解的话，会发现多了一个连接了 $n$ 的点，那么第一问的答案自然就少了一。

这个代码实现就不讲了。

4.$m>0$ 且两问都有的情况

解决了这个情况我们就胜利了。

也就是说现在我们需要解决 $m>0$ 时第二问怎么变化。

按照上面的来就行了。

一.该节点在树中有父节点

按照上面的图，我们可以先将这些节点的贡献去掉。然后再加上新的贡献即可。

二.该节点在树中没有父节点

我们直接去掉 $(a,c)$ 的贡献，然后加上 $(a,b),(b,c)$ 的贡献即可。

这一部分可以参照代码了。

综上，我们解决了所有的问题，接下来贴出代码 $QwQ$ 。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <map>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=1e5+2;
const int MOD=1e9+7;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

int W,n,Ans1,Ans2=1;
vector<int> G[N];
/*G[i]表示与i相连接的点的集合*/
map<pair<int,int>,int> vis;
/*这个是为了方便快速找到代表(a,c)节点所用的map*/

inline void solve() {//初始化
    for(int i=2;i<n;++i) 
        G[i].push_back(i+1),G[i].push_back(i-1);
    G[1].push_back(n),G[1].push_back(2);
    G[n].push_back(n-1),G[n].push_back(1);
    for(int i=1;i<=n;++i) sort(G[i].begin(),G[i].end());
}

int inv[N<<1],fct[N<<1],fci[N<<1];
/*分别对应逆元，阶乘，逆元的阶乘。主要用于计算组合数*/
inline int C(int n,int m) {
    if(n<0||m<0||n<m) return 0;
    return 1ll*fct[n]*fci[m]%MOD*fci[n-m]%MOD;
}
inline int Inv_C(int n,int m) {
    if(n<0||m<0||n<m) return 0;
    return 1ll*fci[n]*fct[m]%MOD*fct[n-m]%MOD;
}
inline int calc(int n,int m) {return C(n+m,n);}
inline int Inv_calc(int n,int m) {return Inv_C(n+m,n);}
/*上面的组合数不再赘述......*/

int root[N],fa[N<<1],sz[N<<1],ch[N<<1][2],tot;
/*root[i]就是S集合中的区间ai,ai+1在树中的节点的编号*/
/*fa表示父节点，sz表示节点子树大小，ch表示节点的左右儿子*/
void dfs(int&x,int f,int l,int r) {
    if(r-l<=1) return;
    x=++tot,sz[x]=1,fa[x]=f;
    int p=lower_bound(G[r].begin(),G[r].end(),l+1)-G[r].begin();
    /*找到这个p*/
    p=G[r][p],vis[make_pair(l,r)]=x;
    /*找到p在原多边形中对应的点，并记录l,r在树中的点的编号*/
    dfs(ch[x][0],x,l,p),dfs(ch[x][1],x,p,r);/*向下计算子树*/
    sz[x]+=sz[ch[x][0]]+sz[ch[x][1]];/*统计子树大小*/
    Ans2=1ll*Ans2*calc(sz[ch[x][0]],sz[ch[x][1]])%MOD;/*计算贡献*/
}

int main() {
    IN(W),IN(n);
    inv[0]=inv[1]=fct[0]=fci[0]=1;
    for(int i=2;i<=n+n;++i) inv[i]=1ll*(MOD-MOD/i)*inv[MOD%i]%MOD;
    for(int i=1;i<=n+n;++i) fct[i]=1ll*fct[i-1]*i%MOD;
    for(int i=1;i<=n+n;++i) fci[i]=1ll*fci[i-1]*inv[i]%MOD;
    /*以上为初始化逆元，阶乘，逆元的阶乘*/
    for(int i=1;i<=n-3;++i) {
        int x,y;IN(x),IN(y);
        G[x].push_back(y),G[y].push_back(x);
    }
    solve(),Ans1=n-1-G[n].size();
    for(int i=0,len=G[n].size();i<len-1;++i) 
        dfs(root[i],0,G[n][i],G[n][i+1]);/*计算每个区间ai,ai+1的树*/
    int Size=0;
    for(int i=0,len=G[n].size();i<len-1;++i) 
        Ans2=1ll*Ans2*calc(Size,sz[root[i]])%MOD,Size+=sz[root[i]];
    /*统计答案*/
    if(!W) printf("%d\n",Ans1);
    else printf("%d %d\n",Ans1,Ans2);
    int q;IN(q);
    while(q--) {
        int a,b;IN(a),IN(b);
        if(a>b) a^=b^=a^=b;
        int x=vis[make_pair(a,b)];/*找到在原树中a,b所代表的节点*/
        if(!W) {printf("%d\n",Ans1-(fa[x]?0:1));continue;}
        else {
            int nowans1=Ans2;
            if(fa[x]) {
                int y=fa[x],k=ch[y][1]==x;
                nowans1=1ll*nowans1*Inv_calc(sz[ch[x][0]],sz[ch[x][1]])%MOD;
                nowans1=1ll*nowans1*Inv_calc(sz[ch[y][0]],sz[ch[y][1]])%MOD;
                nowans1=1ll*nowans1*calc(sz[ch[x][!k]],sz[ch[y][!k]])%MOD;
                nowans1=1ll*nowans1*calc(1+sz[ch[y][!k]]+sz[ch[x][!k]],sz[ch[x][k]])%MOD;
                /*除掉贡献与增加贡献*/
            } else {
                nowans1=1ll*nowans1*Inv_calc(sz[ch[x][0]],sz[ch[x][1]])%MOD;
                nowans1=1ll*nowans1*Inv_calc(Size-sz[x],sz[x])%MOD;
                nowans1=1ll*nowans1*calc(Size-sz[x],sz[ch[x][0]])%MOD;
                nowans1=1ll*nowans1*calc(Size-sz[x]+sz[ch[x][0]],sz[ch[x][1]])%MOD;
                /*除掉贡献与增加贡献*/
            }
            printf("%d %d\n",Ans1-(fa[x]?0:1),nowans1);/*输出答案*/
        }
    }
    return 0;
}

本文标题:【题解】 [HNOI2019]多边形 组合数学 luoguP5288

文章作者:Qiuly

发布时间:2019年04月12日 - 00:00

最后更新:2019年04月12日 - 17:57

原始链接:http://qiulyblog.github.io/2019/04/12/[题解]luoguP5288/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。